var root = {
  val: 3,
  left: {
    val: 9
  },
  right: {
    val: 20,
    left: {
      val: 15
    },
    right: {
      val: 7
    }
  }
}

/**
 * 使用递归的方式
 * 递推的三个条件
 * 1. 递归的基本案例
 * 2. 递推关系
 * 3. 递推终止条件
 * @param {TreeNode} root
 * @return {number[]}
 */
var hasPathSum = function(root, targetSum) {
  if (root == null) return false; // 递推基本案例：节点为空
  if (root.left == null && root.right == null) { // 递推基本案例 遍历到叶子节点
    return targetSum - root.val == 0 // 叶子节点是否为空
  }
  // 递推关系, 将当前节点的左右节点和剩余值，传递给下一个节点
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

console.log(hasPathSum(root, 30))